#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    unordered_map<int, int> dp;
    int dfs(int index)
    {
        if (dp.find(index) == dp.end())
        {
            if (index % 2 == 0)
                dp[index] = dfs(index / 2) + 1;
            else
                dp[index] = dfs(index * 3 + 1) + 1;
        }
        return dp[index];
    }
    int getKth(int lo, int hi, int k) {
        vector<int> res;
        dp[1] = 1;
        for (int i = lo; i <= hi; i++)
        {
            dp[i] = dfs(i);
            res.push_back(i);
        }

        sort(res.begin(), res.end(), [&](int a, int b) {
            if (dfs(a) == dfs(b)) return a < b;
            else return dfs(a) < dfs(b);
            });
        return res[k - 1];
    }
};